using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;

namespace UGent.Tsp
{
    class Subset
    {
        public Subset()
            : this(new Random())
        {
        }

        public Subset(Random random)
        {
            this.random = random;
        }

        private Random random;

        /// <summary>
        /// Selects a random subset of size <c>k</c> from a set of size <c>n</c>.
        /// </summary>
        /// <param name="n">The size of the set from which subsets are drawn.</param>
        /// <param name="k">Number of elements in desired subsets.  <c>k</c> must
        ///    be between 0 and <c>k</c>.</param>
        /// <param name="a"><c>a[i]</c> is the i-th element of the
        ///    output set.  The elements of <c>A</c> are in order</param>
        /// <remarks>
        /// <para>Author: Albert Nijenhuis, Herbert Wilf</para>
        /// <para>FORTRAN90 version by John Burkardt, C# version by Frederik Carlier</para>
        /// <para>Reference: Albert Nijenhuis, Herbert Wilf,
        ///    Combinatorial Algorithms,
        ///    Academic Press, 1978, second edition,
        ///    ISBN 0-12-519260-6.</para>
        /// </remarks>
        public void Random(int n, int k, int[] a)
        {
            if (a == null)
                throw new ArgumentNullException("a");

            if (a.Length != k)
                throw new ArgumentOutOfRangeException("a");

            int ids;
            int ihi;
            int ip;
            int ir;
            int it;
            int ix;
            int l;
            int m;
            int m0;

            if (k < 0)
            {
                throw new ArgumentOutOfRangeException(string.Format("k = {0} but 0 <= k is required.", k));
            }
            else if (n < k)
            {
                throw new ArgumentOutOfRangeException(string.Format("n = {0}, k = {1} but k <= n is required.", n, k));
            }

            if (k == 0)
            {
                return;
            }

            for (int i = 1; i <= k; i++)
            {
                a[i - 1] = ((i - 1) * n) / k;
            }

            for (int i = 1; i <= k; i++)
            {
                while (true)
                {

                    ix = random.Next(1, n + 1);
                    // Note: Upper bound of random number generator
                    // is EXCLUSIVE.

                    l = 1 + (ix * k - 1) / n;

                    if (a[l - 1] < ix)
                    {
                        break;
                    }
                }

                a[l - 1] = a[l - 1] + 1;
            }

            ip = 0;
            it = k;

            for (int i = 1; i <= k; i++)
            {
                m = a[i - 1];
                a[i - 1] = 0;

                if (m != ((i - 1) * n) / k)
                {
                    ip = ip + 1;
                    a[ip - 1] = m;
                }
            }

            ihi = ip;

            for (int i = 1; i <= ihi; i++)
            {
                ip = ihi + 1 - i;
                l = 1 + (a[ip - 1] * k - 1) / n;
                ids = a[ip - 1] - ((l - 1) * n) / k;
                a[ip - 1] = 0;
                a[it - 1] = l;
                it = it - ids;
            }

            ir = 0;
            m0 = 0;
            m = 0;

            for (int ll = 1; ll <= k; ll++)
            {

                l = k + 1 - ll;

                if (a[l - 1] != 0)
                {
                    ir = l;
                    m0 = 1 + ((a[l - 1] - 1) * n) / k;
                    m = (a[l - 1] * n) / k - m0 + 1;
                }

                ix = random.Next(m0, m0 + m);
                // Note: Upper bound of random number generator
                // is EXCLUSIVE.
                //CALL random(ix, m)
                //ix = ix + m0 - 1
                //!! modification by fcarlier
                //!! ix = i4_uniform ( m0, m0 + m - 1, seed )

                int i = l + 1;

                while (i <= ir)
                {
                    if (ix < a[i - 1])
                    {
                        break;
                    }

                    ix = ix + 1;
                    a[(i - 1) - 1] = a[i - 1];
                    i = i + 1;
                }

                a[(i - 1) - 1] = ix;
                m = m - 1;
            }

            return;
        }

        public void Random(int minValue, int maxValue, int count, int[] a)
        {
            // The amount of numbers in the interval
            int length = maxValue - minValue + 1;

            Random(length, count, a);

            for (int i = 0; i < count; i++)
            {
                a[i] += minValue - 1;
            }
        }

        public void PerformanceTester()
        {
            int count = 36; // The amount of random numbers to generate
            int runsPerSweep = 1000000; // The amount of runs per sweep;
            int upper = 100;

            Stopwatch watch = new Stopwatch();
            Random random = new Random();
            Subset subset = new Subset(random);

            while (true)
            {
                watch.Start();
                for (int run = 0; run < runsPerSweep; run++)
                {
                    // Each run, create count random numbers;
                    int[] a = new int[count];
                    subset.Random(upper, count, a);
                }
                watch.Stop();
                Console.WriteLine("Subset: {0}", watch.ElapsedMilliseconds);
                watch.Reset();

                watch.Start();
                for (int run = 0; run < runsPerSweep; run++)
                {
                    // Each run, create count random numbers;
                    for (int number = 0; number < count; number++)
                    {
                        random.Next(1, count);
                    }
                }
                watch.Stop();
                Console.WriteLine("RandomNumbers: {0}", watch.ElapsedMilliseconds);
                watch.Reset();

            }
        }
    }
}
